In Patent Literature 1, a proxy calculation technique is described. Proxy calculation is commissioning another device to perform some calculations. Well-known proxy calculation is requesting a device having a decoding function to decode cipher text and thereby obtaining plain text. For example, assume that a client holds cipher text C obtained by encrypting plain text m by using a public key y and a key device holds a secret key s for the public key y. The client sends the cipher text C to the key device, and the key device obtains the plain text m by decoding the cipher text C by using the secret key s corresponding to the public key y and returns the plain text m to the client. Proxy calculation can solve the problems such as (1) a shortage of calculation capability and functions to be held by the client, (2) leakage of confidential information necessary for the client to execute a function (for example, in an ordinary configuration that does not use proxy calculation, the client themselves has to manage a secret key and there is a possibility that the secret key leaks from the client), and (3) unauthorized use due to loss or theft of a device owned by the client (for example, the key device can stop the decoding function of the client by invalidating the secret key and thereby prevent unauthorized use).
In Non-patent Literatures 1 and 2, key exchange techniques are described. Key exchange is a system for allowing two clients to exchange (share) a key safely by using a communications channel which was made public. As a specific example of key exchange, there is the Diffie-Hellman-Merkle (DHM) key exchange system. In general, although it is possible to perform key exchange by using encryption and decoding, key management is necessary because a secret key is used in encryption and decoding. On the other hand, in the DHM key exchange system, key management becomes unnecessary because random numbers are used in the DHM key exchange system, which improves safety. Moreover, examples of a system that performs key exchange while authenticating the other party with whom a key is shared include authentication key exchange using a digital signature, Menezes-Qu-Vanstone (MQV) authentication key exchange, Hashed MQV (HMQV) authentication key exchange (about these examples, see Non-patent Literature 1), and FSU authentication key exchange (see Non-patent Literature 2).
In Patent Literature 2, a self-correcting technique is described. Self-correction is a technique that always performs correct calculation by using a calculator or a system that does not always output correct calculation results. More specifically, this is a technique that outputs correct calculation results if a calculator that outputs correct calculation results is used and outputs correct calculation results or the results to the effect that calculation is not possible if a calculator that does not always output correct results is used.